package com.cy.algorithm.strpartten;

/**
 * Kmp字符串匹配算法
 *
 * @author chen_yu
 * @date 2020年12月13日18:20:04
 *
 * KMP
 * P模式匹配算法，是一个效率非常高的字符串匹配算法。其全称是Knuth–Morris–Pratt string searching algorithm
 *
 * 其核心思想就是主串不回溯，模式串尽量多地往右移动
 * 即: N(P, j) = {t | prefix(prefix(P, j), t) = suffix(prefix(P, j), t), 0≤ t 〈 j } shift = j -t shift就是本次移动 地最大步长
 * 构建next表
 * 因为空串是任何非空串的真字串，真前缀，真后缀，故只要 j > 0,则必有 0 ∈ N(P, j)。 此时N(P, j) 必非空，从而保证“在其中取最大值”这一操作可行。反之。若j=0,则前缀prefix(P， j) 本身就是空串，它没有真子串，于是必有集合N(P, j) = φ。此种情况下，next[0] 该如何定义呢？
 * 按照串匹配算法的构思，倘若某轮迭代中第一对字符即失配，则应该将模式串P直接右移一位，然后从其首字符继续下一轮对比 就实际效果而言，这一处理方法完全等价于“令next[0] = -1”。
 * 下面以模式串 "ABCDABD" 为例来详细说明是如何构建next表的
 */
public class KmpStringPattern {

    /**
     * 第一步构造next表
     *
     * @param p
     * @return
     */
    public static int[] buildNext(String p) {
        //构建next表就是查找真前缀 == 真后缀的最大长度，以获取模式串尽量多地往右移动
        int[] N = new int[p.length()];
        int m = p.length(), j = 0;//主串位置
        int t = N[0] = -1;//字串位置
        while (j < m - 1) {
            if (t < 0 || p.charAt(j) == p.charAt(t)) {
                j++;
                t++;
                N[j] = t;
            } else {//失配
                t = N[t];
            }
        }
        return N;
    }

    /**
     * 第二步利用next表尽量多地往右移动
     *
     * @param s
     * @param p
     */
    public static void kmp(String s, String p) {
        int[] next = buildNext(p);// 调用next（String p）方法
        int index = -1;// 成功匹配的位置
        int sLength = s.length();// 主串长度
        int pLength = p.length();// 子串长度
        if (sLength < pLength) {
            System.out.println("Error.The main string is greater than the sub string length.");
            return;
        }
        int i = 0;
        int j = 0;
        while (i < sLength && j < pLength) {
            /*
             * 如果j = -1， 或者当前字符匹配成功（即s.charAt(i) == p.charAt(j)）， 都令i++，j++
             * 这两个条件能否交换次序？
             */
            if (j == -1 || s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                /*
                 * 如果j != -1，且当前字符匹配失败， 则令 i 不变，j = next[j], next[j]即为j所对应的next值
                 */
                j = next[j];
            }
        }
        if (j >= pLength) {// 匹配成功
            index = i - j;
            System.out.println("Successful match,index is:" + index);
        } else {// 匹配失败
            System.out.println("Match failed.");
        }
    }
}
